package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 基础数据数组
var count = 0
var items = make([]int, 0)

func Push(n int) int {
	items = append(items, n)
	count++
	FixUp()
	return len(items)
}

func Poll() int {
	if count < 1 {
		return -1
	}
	root := items[0]
	last := items[count-1]
	items[0] = last
	count--
	FixDown()
	return root
}

// 插入元素: 拆入元素后放在数组最后一个位置上
// 将最后一个元素上浮到它应该在的位置
func FixUp() {
	targetNum := count - 1
	for {
		if targetNum <= 0 {
			break
		}
		parentIndex := (targetNum - 1) / 2
		if items[targetNum] > items[parentIndex] {
			break
		}
		items[targetNum], items[parentIndex] = items[parentIndex], items[targetNum]
		targetNum = parentIndex
	}
}

// 取出元素 取出元素后 将最后一个元素放在根元素上
// 元素下沉 将元素移动到它合适的地方
func FixDown() {
	rootIndex := 0
	length := count
	for {
		leftChildIndex := 2*rootIndex + 1
		rightChildIndex := 2*rootIndex + 2

		// 孩子节点中较小的节点
		minChildIndex := leftChildIndex
		// 防止越界
		if leftChildIndex >= length {
			// 至少存在左孩子
			break
		}

		if rightChildIndex < length {
			// 存在 右孩子
			if items[rightChildIndex] < items[leftChildIndex] {
				minChildIndex = rightChildIndex
			}
		}

		if items[rootIndex] <= items[minChildIndex] {
			break
		}
		items[rootIndex], items[minChildIndex] = items[minChildIndex], items[rootIndex]
		rootIndex = minChildIndex
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	for i := 0; i < 10; i++ {
		random := rand.Intn(50)
		fmt.Println(random)
		Push(random)
	}
	fmt.Println(">>>>>>>>>>")
	for range items {
		poll := Poll()
		fmt.Println(poll, ">>>>", cap(items), ">>>>>", len(items))
	}
}
